Từ năm 5 tuổi, Costa đã gia nhập đội thiếu niên của câu lạc bộ bóng đá trong nhà Damaia Ginásio. Bốn năm sau đó, Rui lọt vào tầm ngắm của câu lạc bộ SL Benfica. Chỉ trong vòng 10 phút tập luyện, huyền thoại bóng đá Bồ là Eusébio, người thường phát hiện những tài năng trẻ, đã nhận ra phẩm chất của anh. Cho đến năm 1990, Rui chính thức là cầu thủ của Benfica ở đội hình trẻ. Tuy nhiên mùa bóng đầu tiên anh đã bị cho AD Fafe mượn trong phần lớn thời gian.

Năm 1991, sau cúp thế giới U21, giải đấu mà Bồ Đào Nha đã vô địch sau một cú sút phạt đền của Rui Costa, anh được gọi trở lại Benfica. Tại đây, anh giành được Cúp bóng đá Bồ Đào Nha năm 1993 và quán quân giải vô địch bóng đá Bồ Đào Nha mùa bóng 93-94. Sau 3 mùa giải thành công ở đây, anh được Fiorentina mua lại với giá 1,2 triệu contos (khoảng 6 triệu Euro), một cái giá ấn tượng dành cho một tiền vệ trẻ lúc ấy. Và vụ chuyển nhượng đã thành công.

Rui chơi cho Fiorentina suốt 7 mùa bóng, giúp họ giành Cúp nước Ý 2 lần vào mùa 1995/96 và 2000/01. Lúc này anh và Zidane cạnh tranh với nhau danh hiệu tiền vệ xuất sắc nhất, và Rui Costa được coi là cầu thủ mang áo số 10 hay nhất Serie A trong một thời gian. Việc anh có rời Fiorentina hay không đã gây nhiều tranh luận lúc ấy, khi nhiều câu lạc bộ đều muốn có được chữ ký của anh. Tuy vậy, anh chỉ rời Fiorentina vào cuối mùa 2001/02 khi câu lạc bộ này bị vỡ nợ.

Fatih Terim là huấn luyện viên của Fiorentina trong mùa bóng 2000/2001. Khi cùng Rui Costa rời Fiorentina để tới AC Milan, ông đòi giá chuyển nhượng cho 2 người là 35 triệu Euro. Với việc này, Rui Costa trở thành cầu thủ được Milan mua với giá cao nhất trong lịch sử. Rui Costa chơi 5 mùa bóng cho Milan, tại đây anh có 1 lần vô địch Serie A, 1 lần đoạt Coppa Italia, 1 lần đoạt Siêu cúp nước Ý, 1 lần vô địch UEFA Champions League và 1 lần đoạt Siêu cúp châu Âu.

Rui Costa là một cái tên quan trọng trong 2 mùa bóng đầu ở Milan, nhưng cho đến khi tài năng trẻ Kaká toả sáng, anh dần ít được trọng dụng và phải ngồi ghế dự bị suốt phần lớn buổi hoàng hôn trong sự nghiệp của mình.

Năm 2004, Rui chơi trận đấu cuối cùng trong màu áo Bồ Đào Nha, đó là trận chung kết Euro 2004 mà Bồ Đào Nha đã bị tuyển Hy Lạp đả bại với tỉ số 1-0.

Vào 25 tháng 5 năm 2006, có tin vui cho các cổ động viên SL Benfica, đó là hợp đồng của Rui Costa với AC Milan sẽ chấp dứt, anh thành cầu thủ tự do và ký hợp đồng 1 năm với câu lạc bộ cũ. Tại đây, anh được trả 4,6 triệu Euro cho mùa bóng kèm theo điều khoản có thể gia hạn tiếp 1 năm ở mùa bóng tiếp theo.[1] Rui Costa cho biết anh rất vui với cuộc chuyển nhượng này và sẽ ở lại Benfica cho đến tận cùng sự nghiệp. Ngày 11 tháng 6 năm 2008, Costa chơi trận cuối cùng với Benfica trong trận gặp Vitoria de Setubal, trước khi tuyên bố giải nghệ.

Vài ngày sau đó, Rui Costa trở thành tân giám đốc kỹ thuật của Benfica, sau khi Quique Flores bị sa thải.